package sort

import (
	"traning/algorithm/utility"
)

func HeapSort(arr []int){
	if arr == nil || len(arr) < 2 { return }
	lenArr := len(arr)
	// 从前往后在数组上insert建立大根堆，O(N*logN)
	//for i:=0; i<len(arr); i++ {
	//	insert(arr, i)
	//}
	// 从后往前建立大根堆，O(N)
	for i:=lenArr-1; i>=0 ; i-- {
		heapify(arr, i, lenArr)
	}
	utility.Swap(arr, 0, lenArr-1)
	lenArr--
	for lenArr > 1 {
		heapify(arr, 0, lenArr)
		utility.Swap(arr, 0, lenArr-1)
		lenArr--
	}
}

func insert(arr []int, index int){
	p := (index-1)/2
	for arr[index] > arr[p] {
		utility.Swap(arr, index, p)
		index = p
		p = (index-1)/2
	}
}
// 拓展，原理参考二进制章节：
// p := (index-1) >> 1 可以这么写吗？
// -1:  1111111111111111111111111111111111111111111111111111111111111111
//  1:  0000000000000000000000000000000000000000000000000000000000000001
// >> 带符号右移，go中没有不带符号右移

func heapify(arr []int, index int, size int){
	leftChild := (index<<1) | 1
	bigger := leftChild
	for leftChild < size {
		bigger = leftChild
		if leftChild+1 <size && arr[leftChild] < arr[leftChild+1] {
			bigger = leftChild +1
		}
		if arr[index] > arr[bigger] {
			break
		}
		utility.Swap(arr, index, bigger)
		index = bigger
		leftChild = (index<<1) | 1
	}
}